package ru.ifmo.math.matrix;

import java.util.*;

/**
 * @author avhaliullin
 */
public final class MatrixUtil {
    private MatrixUtil() {
    }

    public static BinaryMatrix identityMatrix(final int size) {
        return new BinaryMatrix() {
            public byte get(int row, int col) {
                return (byte) (row == col ? 1 : 0);
            }

            public int getWidth() {
                return size;
            }

            public int getHeight() {
                return size;
            }
        };
    }

    public static BinaryMatrix concatenateHorizontal(final BinaryMatrix a, final BinaryMatrix b) {
        return new BinaryMatrix() {
            public byte get(int row, int col) {
                if (col < a.getWidth()) {
                    return a.get(row, col);
                } else {
                    return b.get(row, col - a.getWidth());
                }
            }

            public int getWidth() {
                return a.getWidth() + b.getWidth();
            }

            public int getHeight() {
                return a.getHeight();
            }
        };
    }

    public static BinaryMatrix subMatrix(final BinaryMatrix matrix, final int firstRow, final int height, final int firstCol, final int width) {
        return new BinaryMatrix() {
            public byte get(int row, int col) {
                return matrix.get(row + firstRow, col + firstCol);
            }

            public int getWidth() {
                return width;
            }

            public int getHeight() {
                return height;
            }
        };
    }

    public static BinaryMatrix subMatrixInclude(final BinaryMatrix matrix, final List<Integer> rows, final List<Integer> cols) {
        return new BinaryMatrix() {
            public byte get(int row, int col) {
                return matrix.get(rows.get(row), cols.get(col));
            }

            public int getWidth() {
                return cols.size();
            }

            public int getHeight() {
                return rows.size();
            }
        };
    }

    public static BinaryMatrix subMatrixExclude(BinaryMatrix matrix, Integer[] rows, Integer cols[]) {
        List<Integer> includedRows = new ArrayList<Integer>();
        int row = 0;
        for (int i = 0; i < matrix.getHeight(); i++) {
            if (row < rows.length && rows[row].equals(i)) {
                row++;
            } else {
                includedRows.add(i);
            }
        }
        List<Integer> includedCols = new ArrayList<Integer>();
        int col = 0;
        for (int i = 0; i < matrix.getWidth(); i++) {
            if (col < cols.length && cols[col].equals(i)) {
                col++;
            } else {
                includedCols.add(i);
            }
        }
        return subMatrixInclude(matrix, includedRows, includedCols);
    }

    public static BinaryMatrix subMatrixInclude(BinaryMatrix matrix, Integer[] rows, Integer cols[]) {
        return subMatrixInclude(matrix, Arrays.asList(rows), Arrays.asList(cols));
    }

    public static BinaryMatrix subMatrixExclude(BinaryMatrix matrix, List<Integer> rows, List<Integer> cols) {
        return subMatrixExclude(matrix, rows.toArray(new Integer[rows.size()]), cols.toArray(new Integer[cols.size()]));
    }

    public static BinaryMatrix transponate(final BinaryMatrix matrix) {
        return new BinaryMatrix() {
            public byte get(int row, int col) {
                return matrix.get(col, row);
            }

            public int getWidth() {
                return matrix.getHeight();
            }

            public int getHeight() {
                return matrix.getWidth();
            }
        };
    }

    public static Integer[] independentCols(BinaryMatrix matrix) {
        List<Integer> cols = new ArrayList<Integer>();
        List<Integer> rows = new ArrayList<Integer>();

        Set<Integer> freeCols = new HashSet<Integer>();
        for (int i = 0; i < matrix.getWidth(); i++) {
            freeCols.add(i);
        }
        for (int i = 0; i < matrix.getHeight(); i++) {
            rows.add(i);

            for (Integer col : freeCols) {
                cols.add(col);
                int det = determinant(subMatrixInclude(matrix, rows, cols));
                if (det == 0) {
                    cols.remove(cols.size() - 1);
                } else {
                    break;
                }
            }

            if (cols.size() < i + 1) {
                throw new AssertionError("Bad matrix");
            }

            freeCols.remove(cols.get(cols.size() - 1));
        }
        return cols.toArray(new Integer[cols.size()]);
    }

    public static BinaryMatrix swapCols(final BinaryMatrix matrix, final Integer[] newNumeration) {
        return new BinaryMatrix() {
            public byte get(int row, int col) {
                return matrix.get(row, newNumeration[col]);
            }

            public int getWidth() {
                return matrix.getWidth();
            }

            public int getHeight() {
                return matrix.getHeight();
            }
        };
    }

    public static int determinant(BinaryMatrix matrix) {
        if (matrix.getWidth() != matrix.getHeight()) {
            return 0;
        }

        if (matrix.getWidth() == 1) {
            return matrix.get(0, 0);
        }

        int res = 0;
        int sign = 1;
        for (int i = 0; i < matrix.getWidth(); i++) {
            res += sign * determinant(subMatrixExclude(matrix, new Integer[]{0}, new Integer[]{i})) * matrix.get(0, i);
            sign *= -1;
        }
        return res;
    }

    public static byte[][] toArray(BinaryMatrix matrix) {
        byte[][] content = new byte[matrix.getHeight()][matrix.getWidth()];
        for (int i = 0; i < content.length; i++) {
            for (int j = 0; j < content[0].length; j++) {
                content[i][j] = matrix.get(i, j);
            }
        }
        return content;
    }

    private static <T> void swap(T[] array, int i, int j) {
        if (i == j) {
            return;
        }
        T tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static void addToArray(byte[] accum, byte[] add) {
        for (int i = 0; i < add.length; i++) {
            accum[i] = (byte) ((add[i] + accum[i]) % 2);
        }
    }

    public static BinaryMatrix diagonalize(BinaryMatrix matrix) {
        if (matrix.getWidth() < matrix.getHeight()) {
            return transponate(diagonalize(transponate(matrix)));
        }

        int n = Math.min(matrix.getHeight(), matrix.getWidth());

        byte[][] content = toArray(matrix);

        for (int i = 0; i < n; i++) {
            {
                int j = i;
                while (j < n && content[j][i] == 0) {
                    j++;
                }
                if (i == n) {
                    throw new AssertionError("Bad matrix");
                }

                swap(content, i, j);
            }
            for (int j = i + 1; j < n; j++) {
                if (content[j][i] == 1) {
                    addToArray(content[j], content[i]);
                }
            }

        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (content[j][i] == 1) {
                    addToArray(content[j], content[i]);
                }
            }
        }
        return new ArrayMatrix(content);
    }

    public static BinaryMatrix diagonalize2(BinaryMatrix matrix) {
        if (matrix.getWidth() < matrix.getHeight()) {
            return transponate(diagonalize2(transponate(matrix)));
        }

        int n = Math.min(matrix.getHeight(), matrix.getWidth());
        int r = matrix.getWidth() - n;

        byte[][] content = toArray(matrix);

        for (int i = r; i < r + n; i++) {
            {
                int j = i - r;
                while (j < n && content[j][i] == 0) {
                    j++;
                }
                if (j == n) {
                    throw new AssertionError("Bad matrix");
                }

                swap(content, i - r, j);
            }
            for (int j = i + 1 - r; j < n; j++) {
                if (content[j][i] == 1) {
                    addToArray(content[j], content[i - r]);
                }
            }

        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (content[j][i + r] == 1) {
                    addToArray(content[j], content[i]);
                }
            }
        }
        return new ArrayMatrix(content);
    }

    public static BinaryMatrix systematize(BinaryMatrix matrix, List<Transformation> transformations) {
//        Integer[] firstCols = independentCols(matrix);
//        Set<Integer> otherCols = new HashSet<Integer>();
        List<Integer> resList = new ArrayList<Integer>();

        for (int i = 0; i < matrix.getWidth(); i++) {
            resList.add(i);
        }

//        for (int i = 0; i < matrix.getWidth(); i++) {
//            otherCols.add(i);
//        }
//        for (Integer col : firstCols) {
//            otherCols.remove(col);
//            resList.add(col);
//        }
//        resList.addAll(otherCols);
        matrix = swapCols(matrix, resList.toArray(new Integer[resList.size()]));

        final Integer[] backTransformation = new Integer[resList.size()];
        for (int i = 0; i < backTransformation.length; i++) {
            backTransformation[resList.get(i)] = i;
        }
        transformations.add(new Transformation() {
            public BinaryMatrix transform(BinaryMatrix matrix) {
                return swapCols(matrix, backTransformation);
            }
        });
        return diagonalize(matrix);
    }

    public static BinaryMatrix systematize2(BinaryMatrix matrix, List<Transformation> transformations) {
//        Integer[] firstCols = independentCols(matrix);
//        Set<Integer> otherCols = new HashSet<Integer>();
//        List<Integer> resList2 = new ArrayList<Integer>();
//        List<Integer> resList = new ArrayList<Integer>();
//        for (int i = 0; i < matrix.getWidth(); i++) {
//            otherCols.add(i);
//        }
//        for (Integer col : firstCols) {
//            otherCols.remove(col);
//            resList2.add(col);
//        }
//        resList.addAll(otherCols);
//        resList.addAll(resList2);
        List<Integer> resList = new ArrayList<Integer>();

        for (int i = 0; i < matrix.getWidth(); i++) {
            resList.add(i);
        }

        matrix = swapCols(matrix, resList.toArray(new Integer[resList.size()]));
        final Integer[] backTransformation = new Integer[resList.size()];
        for (int i = 0; i < backTransformation.length; i++) {
            backTransformation[resList.get(i)] = i;
        }
        transformations.add(new Transformation() {
            public BinaryMatrix transform(BinaryMatrix matrix) {
                return swapCols(matrix, backTransformation);
            }
        });
        return diagonalize2(matrix);
    }

    public static byte[] multiply(byte[] vector, BinaryMatrix matrix) {
        byte[] res = new byte[matrix.getWidth()];
        for (int i = 0; i < matrix.getWidth(); i++) {
            for (int j = 0; j < vector.length; j++) {
                res[i] = (byte) ((res[i] + (vector[j] * matrix.get(j, i))) % 2);
            }
        }
        return res;
    }

    public static BinaryMatrix multiply(BinaryMatrix a, BinaryMatrix b) {
        if (a.getWidth() != b.getHeight()) {
            throw new AssertionError("Can't multiply");
        }
        int width = b.getWidth();
        int height = a.getHeight();
        byte[][] content = new byte[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                content[i][j] = 0;
                for (int k = 0; k < a.getWidth(); k++) {
                    content[i][j] = (byte) ((content[i][j] + a.get(i, k) * b.get(k, j)) % 2);
                }
            }
        }
        return new ArrayMatrix(content);
    }

    public static String asString(BinaryMatrix matrix) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < matrix.getHeight(); i++) {
            for (int j = 0; j < matrix.getWidth(); j++) {
                res.append(matrix.get(i, j)).append(" ");
            }
            res.append('\n');
        }
        return res.toString();
    }

}
